contents

프림 알고리즘은 가중치가 있는 무방향 연결 그래프에서 최소 신장 트리(Minimum Spanning Tree, MST) 를 찾는 알고리즘입니다. MST는 모든 정점을 사이클 없이 연결하면서 간선 가중치의 합이 최소가 되는 간선들의 부분 집합입니다.

이 알고리즘은 탐욕 알고리즘(greedy algorithm) 으로, 각 단계에서 국소적으로 최적의 선택을 하여 전역 최적해를 찾으려고 시도합니다.

핵심 아이디어 💡

프림 알고리즘은 모든 정점을 포함할 때까지 한 번에 하나의 간선을 추가하며 단일 트리를 키워나가는 방식으로 작동합니다. 임의의 정점에서 시작하여, 각 단계에서 이미 트리에 포함된 정점과 트리 외부에 있는 정점을 연결하는 가장 비용이 적게 드는 간선을 추가합니다.

비유: 여러 마을을 연결하는 도로를 건설해야 한다고 상상해 보세요. 한 마을에서 시작합니다. 각 단계에서 이미 연결된 마을들에서 나가는 모든 가능한 도로를 살펴봅니다. 그중에서 아직 연결되지 않은 마을로 이어지는 가장 짧은 도로를 선택하여 건설합니다. 모든 마을이 연결될 때까지 이 과정을 반복합니다.

알고리즘 단계 🚶‍♂️

1. 초기화:
   • 임의의 시작 정점 s를 선택합니다.
   • MST에 이미 포함된 정점을 추적하기 위한 집합 visited를 만듭니다. 처음에는 비어 있습니다.
   • visited 집합에 있는 임의의 정점에서 아직 방문하지 않은 각 정점까지 도달하는 데 드는 최소 비용을 유지합니다. s까지의 비용은 0으로, 다른 모든 정점까지의 비용은 무한대(∞)로 초기화합니다.
   • (비용, 정점) 쌍을 저장하고 비용으로 정렬하는 우선순위 큐(최소 힙)를 사용합니다. 우선순위 큐에 (0, s)를 추가합니다.
2. 반복: 우선순위 큐가 비어 있지 않은 동안 다음을 반복합니다.
   • 최소값 추출: 우선순위 큐에서 비용이 가장 작은 정점 u를 제거합니다.
   • 방문 확인: 만약 u가 이미 방문되었다면, 건너뛰고 다음 반복으로 넘어갑니다.
   • MST에 추가: u를 방문한 것으로 표시합니다 (visited 집합에 추가). 이 최소 비용으로 u에 도달하는 데 사용된 간선은 이제 MST의 일부가 됩니다. (종종 어떤 간선이나 이전 정점이 이 최소 비용을 만들었는지 저장합니다.) 해당 비용을 총 MST 가중치에 더합니다.
   • 이웃 업데이트: u의 각 이웃 v에 대해 다음을 수행합니다.
     • u와 v를 연결하는 간선의 가중치를 weight(u, v)라고 합니다.
     • 만약 v가 visited 집합에 없고 그리고 weight(u, v)가 현재까지 알려진 v에 도달하는 최소 비용보다 작다면:
       • v에 도달하는 최소 비용을 weight(u, v)로 업데이트합니다.
       • 간선 (u, v)가 이제 v를 MST에 추가할 가능성이 있는 최적의 방법임을 기록합니다.
       • 우선순위 큐에 v를 새로운 더 낮은 비용으로 추가하거나 업데이트합니다: (weight(u, v), v).
3. 종료: 우선순위 큐가 비거나 모든 정점이 방문되면 알고리즘이 종료됩니다. 선택된 간선들이 MST를 형성합니다.

사용되는 자료구조

• 우선순위 큐: 방문한 정점과 방문하지 않은 정점을 연결하는 최소 가중치 간선을 효율적으로 찾는 데 필수적입니다. (비용, 정점) 쌍을 저장합니다.
• 방문 집합/배열: MST에 이미 포함된 정점을 추적합니다.
• 비용/키 배열: 아직 방문하지 않은 각 정점에 도달하는 데 드는 현재까지의 최소 비용을 저장합니다.
• 이전 정점/부모 배열: 각 정점이 어떤 간선을 통해 MST에 포함되었는지 저장하여 최종 MST를 재구성합니다.

시간 복잡도

시간 복잡도는 그래프 표현 방식과 우선순위 큐 구현 방식에 따라 달라집니다.

• 인접 행렬 + 우선순위 큐로 배열 사용: O(V²) - 구현은 간단하지만 희소 그래프에서는 느립니다.
• 인접 리스트 + 이진 힙 (표준 우선순위 큐): O(E log V) - 가장 일반적이고 대체로 효율적입니다. E는 간선의 수, V는 정점의 수입니다. 각 간선은 우선순위 큐 업데이트(log V)를 유발할 수 있으며, 모든 간선을 처리합니다.
• 인접 리스트 + 피보나치 힙: O(E + V log V) - 이론적으로는 더 빠르지만, 피보나치 힙은 상수 인자가 더 크고 구현이 더 복잡합니다.

프림 알고리즘 vs. 크루스칼 알고리즘

두 알고리즘 모두 MST를 찾지만, 접근 방식이 다릅니다.

references